Sublinear-Time Algorithms for Approximating Functions of Many Variables

Mark Iwen, Department of Mathematics, Department of Computational Mathematics, Science and Engineering, Michigan State University, USA

The development of sublinear-time compressive sensing methods for signals which are sparse in Bounded Orthonormal Product Bases (BOPBs) will be discussed. These new methods are obtained from CoSaMP by replacing its usual support identification procedure with a new faster one inspired by fast Sparse Fourier Transform (SFT) techniques. The resulting sub-linearized CoSaMP method allows for the rapid approximation of BOPB-sparse functions of many variables which are too hideously high-dimensional to be learned by other means. Both numeric and theoretical recovery guarantees will be presented. This is joint work with Bosu Choi and Felix Krahmer.

Please direct all questions to the following contacts - Your question will be routed to get you an answer as quickly as possible.

• MSUStatSymposium2018@stt.msu.edu
• Michigan State University
  Department of Statistics and Probability
  Room C413 Wells Hall
  619 Red Cedar Road
  East Lansing, MI 48824